package 二叉树;

public class No110平衡二叉树 {

    /**
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     *
     * 本题中，一棵高度平衡二叉树定义为：
     *
     * 一个二叉树每个节点 的左右两个子树的高度差为0或者1。
     */

    //采用后序遍历,那么复杂度就会是为O(n^1)
    /**
     * 提前阻断思想
     */
    public boolean isBalancedGood(TreeNode root){

        if(root==null){
            return true;
        }

        return levelGood(root)>0;
    }

    private int levelGood(TreeNode node){

        if(node==null){
            return 0;
        }

        int leftHeight = levelGood(node.left);
        int rightHeight = levelGood(node.right);


        if(leftHeight==-1||rightHeight==-1||Math.abs(leftHeight-rightHeight)>1){
            return -1;
        }else{
            return Math.max(leftHeight,rightHeight)+1;
        }
    }

    //自顶向下,有缺陷的做法,这样level会重复被调用 O(n^2)复杂度
    public boolean isBalanced(TreeNode root) {

        if(root==null)
            return true;

        int left=level(root.left,0);
        int right=level(root.right,0);

        if(Math.abs(left-right)>1)
            return false;

        boolean flag1 = isBalanced(root.left);
        boolean flag2 = isBalanced(root.right);

        return flag1&&flag2;//层数是否一样
    }

    private int level(TreeNode node,int deep){
        if(node==null)
            return deep;
        /**
         * 找到左右最深的
         */
        int level1 = level(node.left, deep + 1);
        int level2 = level(node.right, deep + 1);
        return Math.max(level1,level2);
    }

    public static void main(String[] args) {
        No110平衡二叉树 a=new No110平衡二叉树();
        TreeNode node = TreeNode.getNodeByArr(new Integer[]{1, 2,3,4,5,6});
        boolean balanced = a.isBalanced(node);
        System.out.println(balanced);
    }

}
